package BinaryTree;//
// 
// 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则
//，返回 false 。 
//
// 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,4,5,1,2], subRoot = [4,1,2]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// root 树上的节点数量范围是 [1, 2000] 
// subRoot 树上的节点数量范围是 [1, 1000] 
// -10⁴ <= root.val <= 10⁴ 
// -10⁴ <= subRoot.val <= 10⁴ 
// 
// 
// 
// Related Topics 树 深度优先搜索 二叉树 字符串匹配 哈希函数 👍 585 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class isSubtree {

    /**检查两个子树是否相同  和 100相同的树相似*/
    private boolean compare(TreeNode p, TreeNode q){
        if(p==null && q!=null){
            return false;
        }else if(p!=null && q==null){
            return false;
        }else if(p==null && q==null) {
            return true;
        }else if(p.val != q.val){
            //此时两个节点都不空，若值不同，则不同
            return false;
        }
        // 此时就是：两个节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        boolean compareLeft = compare(p.left, q.left);
        boolean compareRight = compare(p.right, q.right);
        return compareLeft && compareRight;

    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        /**
         * 本质一样是看两颗树是否相同，但首先需要从root树中找到第一个和subroot相同开始的节点
         * */
        if(root==null && subRoot!=null){
            return false;
        }
        //遍历root的每一个节点和subroot进行compare,直到有相同的，直接true
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            while(len>0){
                TreeNode curr = queue.poll();
                if(compare(curr,subRoot)){
                    return true;
                }
                if(curr.left!=null){
                    queue.offer(curr.left);
                }
                if(curr.right!=null){
                    queue.offer(curr.right);
                }
                len--;
            }
        }
        return false;
    }


}
//leetcode submit region end(Prohibit modification and deletion)
